#ifndef RAIS_META_BSTREE_HPP
#define RAIS_META_BSTREE_HPP

#include <rais_meta/base.hpp>
#include <rais_meta/list.hpp>

namespace rais {

namespace meta {

namespace bstree_detail {


template <typename Data, typename Left = meta_null, typename Right = meta_null>
struct node {
	using data  = Data;
	using left  = Left;  // left  child
	using right = Right; // right child

}; // struct node

template <typename Node>
constexpr size_t count_size() noexcept{
	if constexpr(std::is_same_v<Node, meta_null>) {
		return 0;
	}else {
		return 1 + count_size<typename Node::left>() + count_size<typename Node::right>();
	}
}

template <typename Node, typename Target, template <typename, typename> class Less>
struct find {


	// assume equal<v1, v2>::value := !Less<v1, v2>::value && !Less<v2, v1>::value
	template <typename T, typename U>
	static constexpr bool equal_v = !Less<T, U>::value && !Less<U, T>::value;
	
	using result = types_pack<
		meta_if<equal_v<typename Node::data, Target>, typename Node::data, 
			typename find<meta_if<Less<typename Node::data, Target>::value, typename Node::right, typename Node::left>, Target, Less>::result
		> 
	>;
};

template <typename Target, template <typename, typename> class Less>
struct find<meta_null, Target, Less> {
	using result = meta_null;
};


// TODO: node to_string meta function
// template <char space_char_ = ' ', char line_feed_char_ = '\n', size_t space_size_ = 4>
// struct to_string_config {
// 	static constexpr char   space       = space_char;
// 	static constexpr char   lf          = line_feed_char;
// 	static constexpr size_t space_size  = space_size_;

// };

// namespace to_string_impl {

// template <typename Node, typename TypeToString = fwarp<op::value_of>, typename Config = to_string_config<>>
// struct to_string {

// 	template <typename String, size_t indent_level = 0>
// };

// } // namespace to_string_impl


namespace put_impl {

template <typename Node, typename NewType, typename Less>
struct rebuild_tree;

template <typename Node, typename NewType, typename Less>
struct rebuild_left {
	using result = node<typename Node::data, typename rebuild_tree<typename Node::left, NewType, Less>::result, typename Node::right>;
};
template <typename NodeData, typename RightChild, typename NewType, typename Less>
struct rebuild_left<node<NodeData, meta_null, RightChild>, NewType, Less> {
	using result = node<NodeData, node<NewType>, RightChild>;
};

template <typename Node, typename NewType, typename Less>
struct rebuild_right {
	using result = node<typename Node::data, typename Node::left, typename rebuild_tree<typename Node::right, NewType, Less>::result>;
};
template <typename NodeData, typename LeftChild, typename NewType, typename Less>
struct rebuild_right<node<NodeData, LeftChild, meta_null>, NewType, Less> {
	using result = node<NodeData, LeftChild, node<NewType>>;
};
template <typename Node, typename...>
struct just_return_node { using result = Node; };

template <typename Node, typename NewType, typename Less>
struct rebuild_tree {
	template <typename T, typename U>
	static constexpr bool equal_v = (!Less::template eval<T, U>::value && !Less::template eval<U, T>::value); 
	
	using result = typename meta_args<Node, NewType, Less>
		::template invoke_if<equal_v<NewType, typename Node::data>, just_return_node >
		::template elif<Less::template eval<NewType, typename Node::data>::value, 
			rebuild_left, 
			rebuild_right
		>::result;

};
template <typename NewType, typename Less>
struct rebuild_tree<meta_null, NewType, Less> {
	// put type
	using result = node<NewType>;
};

template <typename Node, typename Less, typename... NewTypes>
struct put_types {
	// sizeof...(NewTypes) == 0
	using result = Node;
};
template <typename Node, typename Less, typename NewType, typename... NewTypes>
struct put_types<Node, Less, NewType, NewTypes...> {
	using result = typename put_types<typename rebuild_tree<Node, NewType, Less>::result, Less, NewTypes...>::result;
};

} // namespace put_impl

namespace iterator_impl {
template <typename...>
struct iterator;

template <typename... NodeOrData>
struct update_iterator {
	using result = iterator<NodeOrData...>;
};
template <typename Data, typename Left, typename Right, typename... NodeOrData>
struct update_iterator<node<Data, Left, Right>, NodeOrData...> {
	using result = typename update_iterator<Left, Data, Right, NodeOrData...>::result;
};
template <typename Data, typename Right, typename... NodeOrData>
struct update_iterator<node<Data, meta_null, Right>, NodeOrData...> {
	using result = iterator<Data, Right, NodeOrData...>;
};
template <typename Data, typename... NodeOrData>
struct update_iterator<node<Data, meta_null, meta_null>, NodeOrData...> {
	using result = iterator<Data, NodeOrData...>; 
};

template <typename... Nodes>
struct iterator {
	// empty iterator
};
template <typename ThisType, typename... Nodes>
struct iterator<ThisType, Nodes...> {
	// ThisType shouldn't be a node
	static_assert(!is_instantiated_from<ThisType, node>::value, "bad iterator");
	
	using type = ThisType;
	using next = typename update_iterator<Nodes...>::result;
};

} // namespace iterator_impl


// binary search tree
template <typename CompareLess = function_warpper<op::less>, typename Root = meta_null>
struct bstree {

	using root = Root;

	template <typename T, typename U>
	using Less = typename CompareLess::template eval<T, U>; // requires comp<T, U>::value are boolean

	template <typename = meta_null>
	static constexpr size_t size = count_size<Root>();

	using empty = meta_bool<std::is_same_v<root, meta_null>>;

	using begin = typename iterator_impl::update_iterator<root>::result;
	using end   = iterator_impl::iterator<>;


	template <typename Target>
	using find = typename find<root, Target, Less>::first;
 
	template <typename... NewTypes>
	using put  = bstree<CompareLess, typename put_impl::put_types<root, CompareLess, NewTypes...>::result>;

}; // struct bstree



} //namespace bstree_detail

template <typename CompareLess = function_warpper<op::less>, typename Root = meta_null>
using bstree = bstree_detail::bstree<CompareLess, Root>;


} //namespace meta
} //namespace rais


#endif // RAIS_META_BSTREE_HPP
